<?php
/**
 * @title 100145. 统计完全子字符串
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param String $word
     * @param Integer $k
     * @return Integer
     */
    function countCompleteSubstrings($word, $k) {
        /**
         * @since 2023-12-03 超时案例741
         */
        // $word = file_get_contents("/tmp/leetcode/100145.txt");
        // $k = 12210;

        /**
         * @since 2023-12-03 word字符串长度
         */
        $len = strlen($word);

        /**
         * @since 2023-12-03 把字符串变数字型数组，Array[int]
         */
        $numArray = [];
        $aOrd = ord("a");
        for($i=0; $i<$len; $i++){
            $numArray[] = ord($word[$i]) - $aOrd;
        }

        /**
         * @since 2023-12-03 每个数字出现次数n，情况有4种
         * n == 0       00
         * 1 <= n < k   01
         * n == k       10
         * n > k        11
         *
         * 1个数字2位bit，26个数字52位bit
         *
         * 操作实现
         * 当数字第一次出现，加个一个基数base
         * 当数字次数等于k，再加一个基数base
         */
        $baseNumArray = [1];
        for($i=1; $i<26; $i++){
            $baseNumArray[$i] = $baseNumArray[$i-1]<<2;
        }

        /**
         * @since 2023-12-03 符合条件的子字符串数量
         */
        $substringCnt = 0;

        /**
         * @since 2023-12-03 判断数字出现次数是否符合要求，k次
         *
         * 00 AND 01 = 00     n==0次
         * 10 AND 01 = 00     n==k次
         * 01 AND 01 = 01   1<=n<k次
         */
        $numAnd = bindec(str_repeat("01", 26));

        /**
         * @since 2023-12-03 双循环，找符合条件的子字符串
         */
        for($i=0; $i<=($len-$k); $i++){
            /**
             * @since 2023-12-03 52位二进制，记录数字出现次数的情况
             */
            $numBit52 = 0;

            /**
             * @since 2023-12-03 数字出现次数的集合，Array[出现次数]
             */
            $numCntArray = array_fill(0, 26, 0);

            /**
             * @since 2023-12-03 i为起点的子字符串
             */
            for($j=$i; $j<$len; $j++){
                /**
                 * @since 2023-12-03 字母对应数字
                 */
                $num = $numArray[$j];
                // echo PHP_EOL, "[{$i}, {$j}], ", substr($word, $i, $j-$i+1);

                /**
                 * @since 2023-12-03 相邻字母在字母表顺序最多差2
                 */
                if($j>$i){
                    if(abs($num-$numArray[$j-1]) > 2){
                        // echo "，", $word[$j], "与上个字母在字母表顺序差超过2，break", PHP_EOL;
                        break;
                    } else {}
                } else {}
                
                /**
                 * @since 2023-12-03 统计次数
                 */
                $numCntArray[$num] += 1;

                /**
                 * @since 2023-12-03 num出现次数为k
                 */
                if($numCntArray[$num] == $k){
                    /**
                     * @since 2023-12-03 当k=1，直接加2个基数
                     */
                    if($k == 1){
                        $numBit52 += ($baseNumArray[$num]<<1);
                    } else {
                        $numBit52 += $baseNumArray[$num];
                    }
                } elseif($numCntArray[$num] == 1) {
                    /**
                     * @since 2023-12-03 第一次出现，加1个基数
                     */
                    $numBit52 += $baseNumArray[$num];
                } elseif($numCntArray[$num] > $k){
                    /**
                     * @since 2023-12-03 超出k次，不符合要求
                     */
                    // echo "，", $word[$j] ,"出现次数超过{$k}次，break";
                    break;
                } else {
                    /**
                     * @since 2023-12-04 1<$n<$k，当n=1已经变01，无需操作
                     */
                }

                /**
                 * @since 2023-12-03 子字符串长度是k的倍数
                 * @since 2023-12-04 AND，检查所有数字出现次数，是否都是k次
                 */
                if((($j-$i+1)%$k ==0) AND ($numBit52 & $numAnd) == 0){
                    $substringCnt++;
                    // echo "，符合条件, substringCnt={$substringCnt}";
                } else {}
            }
            // echo str_repeat(PHP_EOL, 3);
        }

        /**
         * @return
         */
        return $substringCnt;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202312/2023.12.03_4.php
 */
$datas = [
    ["gvgvvgv", 2], // 1
    // ["abaab", 2], // 2
    // ["igigee", 2], // 3
    // ["aaabbbccc", 3], // 6
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    if(count($data) <= 20){
        var_dump($data);
    } else {
        var_dump(count($data));
    }

    $obj = new Solution();
    $result = $obj->countCompleteSubstrings(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
